|
In graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs. They are named after Paul Erdős and Alfréd Rényi, who first introduced one of the models in 1959;〔〔 the other model was introduced independently and contemporaneously by Edgar Gilbert.〔 In the model introduced by Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely; in the model introduced by Gilbert, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs. == Definition == There are two closely related variants of the Erdős–Rényi (ER) random graph model. *In the ''G''(''n'', ''M'') model, a graph is chosen uniformly at random from the collection of all graphs which have ''n'' nodes and ''M'' edges. For example, in the ''G''(3, 2) model, each of the three possible graphs on three vertices and two edges are included with probability 1/3. *In the ''G''(''n'', ''p'') model, a graph is constructed by connecting nodes randomly. Each edge is included in the graph with probability ''p'' independent from every other edge. Equivalently, all graphs with ''n'' nodes and ''M'' edges have equal probability of :: :The parameter ''p'' in this model can be thought of as a weighting function; as ''p'' increases from 0 to 1, the model becomes more and more likely to include graphs with more edges and less and less likely to include graphs with fewer edges. In particular, the case ''p'' = 0.5 corresponds to the case where all graphs on ''n'' vertices are chosen with equal probability. The behavior of random graphs are often studied in the case where ''n'', the number of vertices, tends to infinity. Although ''p'' and ''M'' can be fixed in this case, they can also be functions depending on ''n''. For example, the statement :Almost every graph in ''G''(''n'', 2ln(''n'')/''n'') is connected. means :As ''n'' tends to infinity, the probability that a graph on ''n'' vertices with edge probability 2ln(''n'')/''n'' is connected, tends to 1. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Erdős–Rényi model」の詳細全文を読む スポンサード リンク
|